package zuochengyun;

import list.ListNode;

public class InsertNodeToSortList {

	/**
	 * 插入num值到有序的环形链表中
	 * @return 返回新的有序的环形链表的头
	 */
	public ListNode insertNum(ListNode head, int num) {
		ListNode node = new ListNode(num);

		if (head == null) {
			node.next = node;
			return node;
		}
		ListNode pre = head;
		ListNode cur = head.next;
		while (cur != head) {
			if (cur.val > num) {
				node.next = pre.next;
				pre.next = node;
				return head;
			} else {
				pre = cur;
				cur = cur.next;
			}
		}
		// 如果重新回到了头结点 ，那么有两种情况： 1->3->4->1... 如果插入5，把5放在1的前面，那么直接返回原来的head即可
		// 如果插入0，那么需要返回0的结点
		node.next = pre.next;
		pre.next = node;
		return head.val < num ? head : node;

	}
}
